\chapter{Вопрос №4}

Урновые схемы и схемы раскладки по ящикам для сочетний и перестановок. Задача о разбиении числа $k$ на $n$ слагаемых.

\section{Сочетания без повторений}

\subsection{Урновая схема}

Имеется урна, в которой $n$ различных шаров, кроме того имеется $k$ неразличимых слотов, в которые мы можем положить шары из урны. Задача - сколькими способами можно заполнить слоты? Ответ: $$ \binom{n}{k} $$

\subsection{Раскладка по ящикам}

Имеется $k$ неразличимых предметов и $n$ различимых ящиков, требуется разложить предметы по ящикам, так чтобы ни в один ящик не попало больше одного предмета. Ответ: $$ \binom{n}{k} $$

\section{Сочетания с повторениями}

\subsection{Урновая схема}

Имеется урна, в которой $n$ различимых шаров, поочередно достаем из урны шары, запоминаем и ложим обратно в урну, сколькими способами можно это проделать? Ответ: $$ \Binomrep{n}{k} $$

\subsection{Раскладка по ящикам}

Имеется $n$ различимых ящиков и $k$ неразличимых предметов, сколькими способами можно разложить предметы по ящикам (ограничения на количество предметов в ящике отсутствуют)? Ответ: $$ \Binomrep{n}{k} $$

\section{Перестановки без повторений}

\subsection{Урновая схема}

Имеется урна с $n$ различимыми предметами. Мы достаем из урны поочередно $k$ предметов и выстраиваем их в линию (согласно порядку, в котором они доставались), сколькими способами можно это сделать? Ответ: $$ \Lowerfact{n}{k} $$

\subsection{Раскладка по ящикам}

Имеется $n$ различных ящиков и $k < n$ различных предметов, сколькими способами можно разложить предметы по ящикам так, чтобы в каждом ящике было не больше одного предмета? Ответ: $$ \Lowerfact{n}{k} $$

\section{Перестановки с повторениями}

\subsection{Урновая схема}

Имеется урна с $n$ различными предметами, мы поочередно достаем $k$ предметов из урны, запоминаем предмет и порядок (номер которым он был вытащен), после чего возвращаем предмет в урну, сколькими способами можно это сделать? Ответ: $$ n^k $$

\subsection{Раскладка по ящикам}

Имеется $n$ различимых ящиков и $k$ различимых предметов, мы раскладываем предметы о ящикам (без ограничений на число предметов в ящике), сколькими способами можно это сделать? Ответ: $$ n^k $$

\section{Разбиение числа $k$ на $n$ слогаемых}

Класс задач о разбиение числа похож на схемы раскладки по ящикам, если представить что у нас имеется набор неразличимых единиц и различимые слогаемые, требуется подсчитать количество способов распределить эти единицы по слагаемым.

При этом оговоримся, что разбиения:
\[
	4 = 3 + 1 = 1 + 3
\]
будем считать различными (это и означает слово разбиение).

\subsection{Первое условие}

Сколькими способами можно представить число $k$ в виде суммы $\sum_{i=1}^n a_i$, где $a_i = 0$ или $a_i = 1$? Ответ: $$ \binom{n}{k} $$

\subsection{Второе условие}

Пусть теперь $a_i \ge 0$, тогда ответ: $$ \Binomrep{n}{k} $$.

\subsection{Третье условие}

Пусть теперь $a_i \ge s_i$ , где $\sum_{i=1}^n s_i = s$, тогда ответ: $$ \Binomrep{n}{k-s}$$
